#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) Huoty, All rights reserved
# Author: Huoty <sudohuoty@163.com>
# CreateTime: 2020-04-15 20:34:40


class BHeap(object):
    """Binary Heap，二叉堆

    这里尝试实现一个最小堆
    """

    def __init__(self):
        self._heap = []

    @property
    def _size(self):
        return len(self._heap)

    def is_empty(self):
        return not self._heap

    def perc_up(self, index):
        """节点上浮"""
        cur_pos = index
        while cur_pos > 0:
            parent = (cur_pos - 1) // 2  # 获取父节点位置
            item = self._heap[cur_pos]
            parent_item = self._heap[parent]
            # 与父节点比较，如果比父节点小，则上浮（即与父节点交换位置）
            if item >= parent_item:
                break

            self._heap[cur_pos], self._heap[parent] = self._heap[parent], self._heap[cur_pos]
            cur_pos = parent

    def add(self, data):
        """添加元素到堆"""
        self._heap.append(data)  # 先将元素插入到堆底
        self.perc_up(self._size - 1)

    def get_min_child(self, index):
        """获取某个节点最小的子节点"""
        lchild = 2 * index + 1
        rchild = 2 * index + 2
        last_index = self._size - 1
        if lchild > last_index:
            raise Exception("位于 %s 的节点没有子节点" % index)
        elif rchild > last_index:
            # 如果没有右节点，就返回左节点
            return lchild
        else:
            # 返回所有节点中值最小的节点的位置
            return lchild if self._heap[lchild] < self._heap[rchild] else rchild

    def perc_down(self, index):
        """节点下沉"""
        lchild = 2 * index + 1
        last_index = self._size - 1
        cur_pos = index
        while lchild <= last_index:
            min_child = self.get_min_child(cur_pos)
            if self._heap[cur_pos] <= self._heap[min_child]:
                break

            self._heap[cur_pos], self._heap[min_child] = self._heap[min_child], self._heap[cur_pos]
            cur_pos = min_child
            lchild = 2 * cur_pos + 1

    def pop(self):
        """弹出堆顶元素"""
        if self.is_empty():
            raise Exception("heap is empty")
        top_item = self._heap[0]
        self._heap[0] = self._heap.pop()
        self.perc_down(0)
        return top_item

    def build_from_sequence(self, sequence):
        """从一个序列构建堆

        在二叉堆中，从数组的中间位置往后的节点都是叶子节点
        利用这个特性，只需将中间位置往前的元素（非叶子节点）下沉
        便可以将一个无需的数组调整为二叉堆
        """
        self._heap = list(sequence)
        mid_index = (self._size - 1) // 2
        for index in range(mid_index, -1, -1):
            self.perc_down(index)


if __name__ == "__main__":
    import random

    lst = [random.randint(0, 20) for _ in range(10)]
    bh = BHeap()
    [bh.add(num) for num in lst]

    print(lst)
    print(bh._heap)
    sorted_lst = []
    while True:
        try:
            sorted_lst.append(bh.pop())
        except Exception:
            break
    print(sorted_lst)

    bh2 = BHeap()
    bh2.build_from_sequence(lst)
    print(bh2._heap)
